package it.storm.solution;

import java.util.ArrayList;
import java.util.List;

/**
 * 54. 螺旋矩阵
 * https://leetcode-cn.com/problems/spiral-matrix/
 */
public class Solutions_54 {
    public static void main(String[] args) {
        int[][] matrix1 = {{1, 2, 3}, {4, 5, 6}, {7, 8, 9}};
        // output: {1, 2, 3, 6, 9, 8, 7, 4, 5}

        int[][] matrix2 = {{1, 2, 3, 4}, {5, 6, 7, 8}, {9, 10, 11, 12}};
        // output: {1, 2, 3, 4, 8, 12, 11, 10, 9, 5, 6, 7}

        int[][] matrix3 = {{3}, {2}};
        // output: {3, 2}

        int[][] matrix4 = {{7}, {9}, {6}};
        // output: {7, 9, 6}

        int[][] matrix5 = {{2, 5, 8}, {4, 0, -1}};
        // output: {2, 5, 8, -1, 0, 4}

        List<int[][]> inputs = new ArrayList<>();
        inputs.add(matrix1);
        inputs.add(matrix2);
        inputs.add(matrix3);
        inputs.add(matrix4);
        inputs.add(matrix5);

        for (int[][] input : inputs) {
            List<Integer> result = spiralOrder(input);
            System.out.println(result);
        }
    }

    /**
     * 由外层向内层逐圈遍历
     * 关键：定义上、下、左、右四个索引
     */
    public static List<Integer> spiralOrder(int[][] matrix) {
        List<Integer> list = new ArrayList<>();
        // 上、下、左、右 索引
        int up = 0, down = matrix.length -1;
        int left = 0, right = matrix[0].length - 1;

        while (true) {
            // 取得 up 行元素
            for (int i = left; i <= right; i++) {
                list.add(matrix[up][i]);
            }
            up ++;

            if (up > down) {
                break;
            }

            // 取得 right 列元素
            for (int i = up; i <= down; i++) {
                list.add(matrix[i][right]);
            }
            right --;

            if (right < left) {
                break;
            }

            // 取得 down 行元素
            for (int i = right; i >= left; i--) {
                list.add(matrix[down][i]);
            }
            down --;

            if (down < up) {
                break;
            }

            // 取得 left 列元素
            for (int i = down; i >= up; i--) {
                list.add(matrix[i][left]);
            }
            left ++;

            if (left > right) {
                break;
            }
        }
        return list;
    }
}
